package zhengqc.sort.quick_sort;
import zhengqc.sort.Sort;

import java.util.Random;

public class TwoWayQuickSort<E extends Comparable<E>> extends Sort<E> {
    private Random random;
    public TwoWayQuickSort() {
        this.sortName = "TwoWayQuickSort";
        this.random = new Random();
    }
    @Override
    public void sort(E[] array) {
        sort(array, 0, array.length-1);
    }
    private void sort(E[] array, int left, int right) {
        if (left >= right) return;
        int p = partition(array, left, right);
        sort(array, left, p-1);
        sort(array, p+1, right);
    }
    private int partition(E[] array, int left, int right) {
        // 生成 [left, right] 之间的随机索引
        int p = left + random.nextInt(right-left+1);
        swap(array, left, p);
        int i = left+1, j = right;
        // 循环不变量 array[left+1...j] <= v, array[j+1...i] >= v
        while (true) {
            while ( (i <= j) && (array[i].compareTo(array[left]) < 0) )
                ++i;
            while ( (i <= j) && (array[j].compareTo(array[left]) > 0) )
                --j;
            if ( i >= j ) break;
            swap(array, i, j);
            i++; j--;
        }
        swap(array, left, j);
        return j;
    }
    private static <E> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
